/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/interleaving-string
   @Language: C++
   @Datetime: 16-02-09 05:54
   */

// Method 1, DP, Time 23ms
class Solution {
public:
	/**
	 * Determine whether s3 is formed by interleaving of s1 and s2.
	 * @param s1, s2, s3: As description.
	 * @return: true of false.
	 * Tip: Using DP[i][j] as:
	 *      select range [0,i) in s1 and [0,j) in s2,
	 *      combine a new str to match range [0,i+j) in s3.
	 *      has two stations:
	 *          s1 [0,i-1) + s2 [0,j), and current select i in s1
	 *          s2 [0,j-1) + s1 [0,i), and current select j in s2
	 *          if s1[i-1]==s3[i+j-1], and DP[i-1][j] is 1, DP[i][j]=1;
	 *          if s2[j-1]==s3[i+j-1], and DP[i][j-1] is 1, DP[i][j]=1;
	 */
	bool isInterleave(string s1, string s2, string s3) {
		// write your code here
		int len1=s1.length(),len2=s2.length(),len3=s3.length();
		if (len1+len2!=len3) return false;
		if (len1==0) return s2==s3;
		if (len2==0) return s1==s3;
		vector<vector<bool> > dp(len1+1,vector<bool>(len2+1,false));
		dp[0][0]=true;
		for(int i=1; i<=len1 && dp[i-1][0]; ++i)
			dp[i][0] = s1[i-1]==s3[i-1];	// only use s1
		for(int i=1; i<=len2 && dp[0][i-1]; ++i)
			dp[0][i] = s2[i-1]==s3[i-1];	// only use s2
		for(int i=1; i<=len1; ++i)
			for(int j=1; j<=len2; ++j){
				if (s1[i-1]==s3[i+j-1]) dp[i][j]=dp[i][j]|dp[i-1][j];
				if (s2[j-1]==s3[i+j-1]) dp[i][j]=dp[i][j]|dp[i][j-1];
			}
		return dp[len1][len2];
	}
};

// Method 2, DFS, Time 21ms
class Solution {
	bool isMerge(const string &s1, const string &s2,
			int i, int j, const string &s3){
		if (i==s1.length() && j==s2.length()) return true;
		if (i>s1.length() || j>s2.length()) return false;
		if (i<s1.length() && s1[i]==s3[i+j] && isMerge(s1,s2,i+1,j,s3))
			return true;
		if (j<s2.length() && s2[j]==s3[i+j] && isMerge(s1,s2,i,j+1,s3))
			return true;
		return false;
	}

public:
	/**
	 * Determine whether s3 is formed by interleaving of s1 and s2.
	 * @param s1, s2, s3: As description.
	 * @return: true of false.
	 */
	bool isInterleave(string s1, string s2, string s3) {
		// write your code here
		if (s1.length()+s2.length()!=s3.length()) return false;
		return isMerge(s1,s2,0,0,s3);
	}
};
